// 版权所有2011 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// lzw包实现了Lempel-Ziv-Welch压缩数据格式，
// 如T.A.Welch所述，“高性能数据技术
// 压缩”，计算机，17（6）（1984年6月），第8-19页。
// 
// 尤其是，它实现了GIF和PDF文件
// 格式所使用的LZW，这意味着最多12位的可变宽度代码和第一个
// 两个非文字代码是清晰代码和EOF代码。
// 
// TIFF文件格式使用与LZW 
// 算法类似但不兼容的版本。看看戈朗。org/x/image/tiff/lzw包，用于
// 实现。
package lzw

// TODO（nigeltao）：检查PDF是否以与GIF相同的方式使用LZW，
// 模LSB/MSB打包顺序。

import (
	"bufio"
	"errors"
	"fmt"
	"io"
)

// 顺序指定LZW数据流中的位顺序。
type Order int

const (
	// LSB表示最低有效位优先，如GIF文件格式中所用。
	LSB Order = iota
	// MSB表示最高有效位优先，在TIFF和PDF 
	// 文件格式中使用。
	MSB
)

const (
	maxWidth           = 12
	decoderInvalidCode = 0xffff
	flushBuffer        = 1 << maxWidth
)

// 读卡器是一个io。读取器，可用于读取
// LZW格式的压缩数据。
type Reader struct {
	r        io.ByteReader
	bits     uint32
	nBits    uint
	width    uint
	read     func(*Reader) (uint16, error) // readLSB或readMSB 
	litWidth int                           // 以位表示的文字代码宽度
	err      error

	// 前1个<<litWidth代码是文字代码。
	// 接下来的两个代码表示清除和EOF。
	// 其他有效代码在[lo，hi]范围内，其中lo:=clear+2，
	// 看到的每个代码的上限都会递增。
	// 
	// 溢出是hi溢出代码宽度的代码。它总是
	// 等于1<<宽度。
	// 
	// 最后一个是最近看到的代码，或decoderInvalidCode。
	// 
	// 一个不变量是hi<溢出。
	clear, eof, hi, overflow, last uint16

	// 在[lo，hi]中的每个代码c扩展到两个或更多字节。对于c！=嗨：
	// 后缀[c]是这些字节中的最后一个。
	// 前缀[c]是除最后一个字节外的所有字节的代码。
	// 此代码可以是文字代码，也可以是[lo，c]
	// c==hi是一种特殊情况。
	suffix [1 << maxWidth]uint8
	prefix [1 << maxWidth]uint16

	// 输出是临时输出缓冲区。
	// 从缓冲区开始累积文字代码。
	// 非文字代码解码为一系列后缀，这些后缀首先是
	// 从缓冲区末尾从右向左写入，然后复制
	// 到缓冲区的开头。
	// 当它包含>=1<<maxWidth字节时，它会被刷新，因此始终有空间解码整个代码。
	output [2 * 1 << maxWidth]byte
	o      int    // 将索引写入输出
	toRead []byte // 从读取返回的字节
}

// readLSB返回“最低有效位优先”数据的下一个代码。
func (r *Reader) readLSB() (uint16, error) {
	for r.nBits < r.width {
		x, err := r.r.ReadByte()
		if err != nil {
			return 0, err
		}
		r.bits |= uint32(x) << r.nBits
		r.nBits += 8
	}
	code := uint16(r.bits & (1<<r.width - 1))
	r.bits >>= r.width
	r.nBits -= r.width
	return code, nil
}

// readMSB返回“最高有效位优先”数据的下一个代码。
func (r *Reader) readMSB() (uint16, error) {
	for r.nBits < r.width {
		x, err := r.r.ReadByte()
		if err != nil {
			return 0, err
		}
		r.bits |= uint32(x) << (24 - r.nBits)
		r.nBits += 8
	}
	code := uint16(r.bits >> (32 - r.width))
	r.bits <<= r.width
	r.nBits -= r.width
	return code, nil
}

// 读取io。读卡器，从底层读卡器读取未压缩的字节。
func (r *Reader) Read(b []byte) (int, error) {
	for {
		if len(r.toRead) > 0 {
			n := copy(b, r.toRead)
			r.toRead = r.toRead[n:]
			return n, nil
		}
		if r.err != nil {
			return 0, r.err
		}
		r.decode()
	}
}

// decode从r解压字节，并将它们保留在d.toRead中。
// read指定如何将字节解码为代码。
// litWidth是以位为单位的文字代码宽度。
func (r *Reader) decode() {
	// 在代码流上循环，将代码转换为解压缩字节。
loop:
	for {
		code, err := r.read(r)
		if err != nil {
			if err == io.EOF {
				err = io.ErrUnexpectedEOF
			}
			r.err = err
			break
		}
		switch {
		case code < r.clear:
			// 我们有一个文字代码。
			r.output[r.o] = uint8(code)
			r.o++
			if r.last != decoderInvalidCode {
				// 保存hi代码扩展到的内容。
				r.suffix[r.hi] = uint8(code)
				r.prefix[r.hi] = r.last
			}
		case code == r.clear:
			r.width = 1 + uint(r.litWidth)
			r.hi = r.eof
			r.overflow = 1 << r.width
			r.last = decoderInvalidCode
			continue
		case code == r.eof:
			r.err = io.EOF
			break loop
		case code <= r.hi:
			c, i := code, len(r.output)-1
			if code == r.hi && r.last != decoderInvalidCode {
				// code==hi是一个特例，它扩展到最后一个扩展
				// 后面是最后一个扩展的头。为了找到头部，我们沿着前缀链走
				// 直到找到一个文字代码。
				c = r.last
				for c >= r.clear {
					c = r.prefix[c]
				}
				r.output[i] = uint8(c)
				i--
				c = r.last
			}
			// 将后缀链复制到输出中，然后将其写入w。
			for c >= r.clear {
				r.output[i] = r.suffix[c]
				i--
				c = r.prefix[c]
			}
			r.output[i] = uint8(c)
			r.o += copy(r.output[r.o:], r.output[i:])
			if r.last != decoderInvalidCode {
				// 保存hi代码扩展到的内容。
				r.suffix[r.hi] = uint8(c)
				r.prefix[r.hi] = r.last
			}
		default:
			r.err = errors.New("lzw: invalid code")
			break loop
		}
		r.last, r.hi = code, r.hi+1
		if r.hi >= r.overflow {
			if r.hi > r.overflow {
				panic("unreachable")
			}
			if r.width == maxWidth {
				r.last = decoderInvalidCode
				// 撤销上面几行的d.hi++，以便（1）我们维护
				// d.hi<d.overflow的不变量，以及（2）d.hi不
				// 最终使uint16溢出。
				r.hi--
			} else {
				r.width++
				r.overflow = 1 << r.width
			}
		}
		if r.o >= flushBuffer {
			break
		}
	}
	// 刷新挂起的输出。
	r.toRead = r.output[:r.o]
	r.o = 0
}

var errClosed = errors.New("lzw: reader/writer is closed")

// Close关闭读卡器，并为以后的任何读取操作返回一个错误。
// 它不会关闭基础io。读者
func (r *Reader) Close() error {
	r.err = errClosed // 如果出现任何读取
	return nil
}

// 重置将清除读卡器的状态，并允许它作为新的读卡器再次使用
// 。
func (r *Reader) Reset(src io.Reader, order Order, litWidth int) {
	*r = Reader{}
	r.init(src, order, litWidth)
}

// NewReader创建一个新io。读近一点。
// 读取返回的io。ReadCloser从r.
// 读取和解压缩数据，如果r不实现io。拜特瑞德，
// 解压器可能从r.
// 读取的数据超过需要。当
// 读取完毕时，调用方有责任在ReadCloser上调用Close。
// 用于文字代码的位数litWidth必须在
// 范围[2,8]内，通常为8。它必须等于压缩过程中使用的宽度
// 。
// 
// 保证返回io的基础类型。ReadCloser 
// 是一个*阅读器。
func NewReader(r io.Reader, order Order, litWidth int) io.ReadCloser {
	return newReader(r, order, litWidth)
}

func newReader(src io.Reader, order Order, litWidth int) *Reader {
	r := new(Reader)
	r.init(src, order, litWidth)
	return r
}

func (r *Reader) init(src io.Reader, order Order, litWidth int) {
	switch order {
	case LSB:
		r.read = (*Reader).readLSB
	case MSB:
		r.read = (*Reader).readMSB
	default:
		r.err = errors.New("lzw: unknown order")
		return
	}
	if litWidth < 2 || 8 < litWidth {
		r.err = fmt.Errorf("lzw: litWidth %d out of range", litWidth)
		return
	}

	br, ok := src.(io.ByteReader)
	if !ok && src != nil {
		br = bufio.NewReader(src)
	}
	r.r = br
	r.litWidth = litWidth
	r.width = 1 + uint(litWidth)
	r.clear = uint16(1) << uint(litWidth)
	r.eof, r.hi = r.clear+1, r.clear+1
	r.overflow = uint16(1) << r.width
	r.last = decoderInvalidCode
}
